#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;


 //Definition for a binary tree node.
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };


class Solution1 {
	vector<string> ans;
	vector<int> path;

	void backtracking(TreeNode* root)
	{
		path.push_back(root->val);

		if (root->left == nullptr && root->right == nullptr)
		{
			string spath;
			for (size_t i = 0; i < path.size() - 1; i++)
			{
				spath += to_string(path[i]);
				spath += "->";
			}
			spath += to_string(path.back());
			ans.push_back(spath);
			return;
		}

		if (root->left)
		{
			backtracking(root->left);
			path.pop_back();
		}

		if (root->right)
		{
			backtracking(root->right);
			path.pop_back();
		}
	}
public:
	vector<string> binaryTreePaths(TreeNode* root) {
		if (root == nullptr)
		{
			return ans;
		}

		backtracking(root);

		return ans;
	}
};

class Solution2 {
public:
	int sumOfLeftLeaves(TreeNode* root) {
		if (root == nullptr)  return 0;
		if (root->left == nullptr && root->right == nullptr) return 0;

		int leftLeft = sumOfLeftLeaves(root->left);
		if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr)
		{
			leftLeft = root->left->val;
		}

		int rightLeft = sumOfLeftLeaves(root->right);

		return leftLeft + rightLeft;
	}
};

class Solution3 {
public:
	int findBottomLeftValue(TreeNode* root) {
		queue<TreeNode*> q;
		q.push(root);

		int bottomLeft = 0;
		while (!q.empty())
		{
			int size = q.size();
			for (size_t i = 0; i < size; i++)
			{
				TreeNode* cur = q.front();
				q.pop();
				if (i == 0) { bottomLeft = cur->val; }
				if (cur->left != nullptr) { q.push(cur->left); }
				if (cur->right != nullptr) { q.push(cur->right); }
			}
		}

		return bottomLeft;
	}
};

class Solution4 {
	int maxDepth = INT_MIN;
	int ans = 0;

	void backtracing(TreeNode* root, int depth)
	{
		if (root->left == nullptr && root->right == nullptr) {
			if (depth > maxDepth) {
				maxDepth = depth;
				ans = root->val;
			}
			return;
		}

		if (root->left) {
			depth++;
			backtracing(root->left, depth);
			depth--;
		}

		if (root->right) {
			depth++;
			backtracing(root->right, depth);
			depth--;
		}
	}
public:
	int findBottomLeftValue(TreeNode* root) {
		backtracing(root, 0);
		return ans;
	}
};

class Solution5 {
	bool backtracking(TreeNode* root, int targetSum)
	{
		if (root->left == nullptr && root->right == nullptr && targetSum == 0) return true;
		if (root->left == nullptr && root->right == nullptr) return false;

		if (root->left)  {
			targetSum -= root->left->val;
			if (backtracking(root->left, targetSum) == true) {
				return true;
			}
			targetSum += root->left->val;
		}

		if (root->right) {
			targetSum -= root->right->val;
			if (backtracking(root->right, targetSum) == true) {
				return true;
			}
			targetSum += root->right->val;
		}

		return false;
	}
public:
	bool hasPathSum(TreeNode* root, int targetSum) {
		if (root == nullptr)  return false;

		return backtracking(root, targetSum - root->val);
	}
};

class solution6 {
public:
	bool hasPathSum(TreeNode* root, int sum) {
		if (root == nullptr) return false;
		if (!root->left && !root->right && sum == root->val) {
			return true;
		}
		return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
	}
};

class Solution7 {
public:
	TreeNode* reCreateTree(const vector<int>& inorder, int inStart, int inEnd
		, const vector<int>& postorder, int postStart, int postEnd)
	{
		if (inStart > inEnd || postStart > postEnd)
		{
			return nullptr;
		}
		TreeNode* root = new TreeNode(postorder[postEnd]);
		for (size_t i = inStart; i <= inEnd; i++)
		{
			if (inorder[i] == postorder[postEnd])
			{
				root->left = reCreateTree(inorder, inStart, i - 1
					, postorder, postStart, postStart + i - 1 - inStart);
				root->right = reCreateTree(inorder, i + 1, inEnd
					, postorder, postStart + i - inStart, postEnd - 1);
				break;
			}
		}
		return root;
	}
	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
		if (inorder.empty() || postorder.empty())
		{
			return nullptr;
		}
		return reCreateTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
	}
};

class Solution8 {
public:
	bool IsPalindrome(const string& str, int left, int right) {
		while (left < right) {
			if (str[left] != str[right]) {
				return false;
			}
			left++;
			right--;
		}
		return true;
	}

	int minCut(string s) {
		if (s.empty()) {
			return 0;
		}

		vector<int> dp(s.size() + 1);
		for (int i = 0; i < dp.size(); i++) {
			dp[i] = i - 1;
		}

		for (int i = 1; i < dp.size(); i++) {
			for (int j = 0; j < i; j++) {
				if (IsPalindrome(s, j, i - 1)) {
					dp[i] = min(dp[i], 1 + dp[j]);
				}
			}
		}

		return dp[dp.size() - 1];
	}
};




int main()
{
	return 0;
}